#include <stdio.h>
#include <stdlib.h>
//单链表的应用——删除链表的中间节点（快慢指针）
typedef int ElemType;
typedef struct node
{
    ElemType data;
    struct node *next;
}Node;
Node *Initlist()
{
    Node *s=(Node *)malloc(sizeof(Node));
    s->data=0;
    s->next=NULL;
    return s;
}
void addtail(Node *ps,ElemType n)
{
    Node*p=ps;
    while(p->next)
    {
        p=p->next;
    }
    Node * q=(Node*)malloc(sizeof(Node));
    q->data=n;
    p->next=q;
    q->next=NULL;
}
void printlist(Node *ps)
{
    Node *p=ps->next;
    while(p)
    {
        printf("%d ",p->data);
        p=p->next;
    }
}
//删除中间节点：偶数个时取靠后面的节点
//让快指针指向首元节点，慢指针指向头节点
//一起出发，快指针每次走两步，慢指针每次走一步
//快指针指向NULL或指向尾节点时，慢指针指向中间节点的前一个
void shanchumid(Node *ps)
{
    Node*first=ps->next;
    Node *slow=ps;
    while(first!=NULL&&first->next!=NULL)
    {
        first=first->next->next;
        slow=slow->next;
    }
    Node*mid=slow->next;
    slow->next=mid->next;
    free(mid);
}
//释放链表(头节点也被释放)
void freelist(Node *ps)
{
    Node *p=ps;
    Node *q;
    while(p)
    {
        q=p->next;
        free(p);
        p=q;
    }
}
int main()
{
    Node *list=Initlist();
    addtail(list,1);
    addtail(list,2);
    addtail(list,3);
    addtail(list,4);
    addtail(list,5);
    addtail(list,6);
    printlist(list);
    //删除中间节点
    shanchumid(list);
    printlist(list);
    freelist(list);
    return 0;
}